package com.computer.fundamentals.algorithm;

/**Terminus
 * 经典问题——24点
 *  -----------------------------------------------------------------------------------------------
 *  任意给定四个整数, 用加、减、乘、除以及适当的括号连接, 无论顺序, 使计算结果为24, 也可能根本就无解。
 *  -----------------------------------------------------------------------------------------------
 */
public class TwentyFourPoint {

    public boolean flag; // 分母0的标记

    /**
     * 解决方案：
     *  方案一：穷举法
     *      将四个整数以及四个运算符的所有排列全部列举出来, 然后分别计算：
     *      1. 四个整数位置的排列, 用0,1,2,3表示四个数的位置, 重复的排列可以认为是无效的, 那么有24种排列方案(4!)
     *      2. 三个运算符的插入位置, 因为运算符可以随意插入不限制重复次数, 因此有64种插入方案(4^3)
     *      3. 假设四个数的排列和运算符的结构为 a ① b ② c ③ d, 那么运算符的顺序有6种：
     *          ① ② ③; ① ③ ②; ② ① ③; ② ③ ①; ③ ① ②; ③ ② ①
     *          其等价的表达式为：
     *          I:   ((a ① b) ② c) ③ d
     *          II:  (a ① b) ② (c ③ d)
     *          III: (a ① (b ② c)) ③ d
     *          IV:  a ① ((b ② c) ③ d)
     *          V:   (a ① b) ② (c ③ d)
     *          VI:  a ① (b ② (c ③ d))
     *          其中II和V是相同的, 因此所有运算符仅需要考虑五种顺序结构
     *      综上, 通过逐一计算即可得到所有可能的结果
     */
    public void solution(int[] nums) {
        int n = nums.length;
        char[] signal = new char[] {'-', '+', '*', '/'};
        int count = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                for (int k = 0;k < n;k++) {
                    for (int l = 0;l < n;l++) {
                        if (i == j || i == k || i == l || j == k || j == l || k == l) {
                            continue;
                        }
                        int num1 = nums[i];
                        int num2 = nums[j];
                        int num3 = nums[k];
                        int num4 = nums[l];
                        for (char ch1 : signal) {
                            for (char ch2 : signal) {
                                for (char ch3 : signal) {
                                    double t1;
                                    double t2;
                                    double t3;
                                    // 情形1
                                    t1 = calculate(ch1, num1, num2);
                                    t2 = calculate(ch2, t1, num3);
                                    t3 = calculate(ch3, t2, num4);
                                    if (flag) {
                                        flag = false;
                                        continue;
                                    }
                                    if (t3 == 24.0) {
                                        count++;
                                        System.out.printf(
                                                "((%d %c %d) %c %d) %c %d%n",
                                                num1, ch1, num2, ch2, num3, ch3, num4
                                        );
                                    }

                                    // 情形2
                                    t1 = calculate(ch1, num1, num2);
                                    t2 = calculate(ch3, num3, num4);
                                    t3 = calculate(ch2, t1, t2);
                                    if (flag) {
                                        flag = false;
                                        continue;
                                    }
                                    if (t3 == 24.0) {
                                        count++;
                                        System.out.printf(
                                                "(%d %c %d) %c (%d %c %d)%n",
                                                num1, ch1, num2, ch2, num3, ch3, num4
                                        );
                                    }

                                    // 情形3
                                    t1 = calculate(ch2, num2, num3);
                                    t2 = calculate(ch1, num1, t1);
                                    t3 = calculate(ch3, t2, num4);
                                    if (flag) {
                                        flag = false;
                                        continue;
                                    }
                                    if (t3 == 24.0) {
                                        count++;
                                        System.out.printf(
                                                "((%d %c (%d %c %d)) %c %d%n",
                                                num1, ch1, num2, ch2, num3, ch3, num4
                                        );
                                    }


                                    // 情形4
                                    t1 = calculate(ch2, num2, num3);
                                    t2 = calculate(ch3, t1, num4);
                                    t3 = calculate(ch1, num1, t2);
                                    if (flag) {
                                        flag = false;
                                        continue;
                                    }
                                    if (t3 == 24.0) {
                                        count++;
                                        System.out.printf(
                                                "%d %c ((%d %c %d) %c %d)%n",
                                                num1, ch1, num2, ch2, num3, ch3, num4
                                        );
                                    }

                                    // 情形5
                                    t1 = calculate(ch3, num3, num4);
                                    t2 = calculate(ch2, num2, t1);
                                    t3 = calculate(ch1, num1, t2);
                                    if (flag) {
                                        flag = false;
                                        continue;
                                    }
                                    if (t3 == 24.0) {
                                        count++;
                                        System.out.printf(
                                                "%d %c (%d %c (%d %c %d))%n",
                                                num1, ch1, num2, ch2, num3, ch3, num4
                                        );
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        System.out.println("24点计算方案总数为：" + count);
    }

    /**
     * 符号运算
     */
    public double calculate(char ch1, double num1, double num2) {
        switch (ch1) {
            case '-': return num1 - num2;
            case '+': return num1 + num2;
            case '*': return num1 * num2;
        }
        if (num2 == 0) {
            flag = true;
            return -1;
        }else {
            return num1 / num2;
        }
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        TwentyFourPoint twentyFourPoint = new TwentyFourPoint();
        twentyFourPoint.solution(new int[] {-2, 8, 9, 10});
    }

}